package _32define;

public class Demo2 {
    public static boolean hasCycle(Node head) {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next  != null) {
            slow = slow.next ;
            fast = fast.next.next ;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
    public static Node findCycleStart(Node head) {
        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next  != null) {
            slow = slow.next ;
            fast = fast.next.next ;
            if (slow == fast) {
                break;
            }
        }

        int length = 1;
        fast = fast.next ;
        while (slow != fast) {
            fast = fast.next ;
            length++;
        }

        slow = head;

        for (int i = 0; i < length; i++) {
            slow = slow.next ;
        }

        return slow;
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next  = new Node(2);
        head.next.next  = new Node(3);
        head.next.next.next  = new Node(4);
        head.next.next.next.next  = head.next ;

        if (hasCycle(head)) {
            Node startOfCycle = findCycleStart(head);
            System.out.println ("环的起始位置是: " + startOfCycle.data );
        } else {
            System.out.println ("链表中没有环");
        }
    }
}

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data  = data;
        this.next  = null;
    }
}

